package algorithm.sliding_window;

import java.util.*;

/**
 * 滑动窗口的模板算法
 */
public class Template {

    // 滑动窗口模板中，窗口的滑动主要通过两个指针（通常称为左指针和右指针）来实现。
    // 1. 初始化指针和相关变量
    // 1.1 首先，初始化左指针left和右指针right都为0，表示窗口的起始位置在数组的第一个元素处。
    // 1.2 根据具体问题初始化其他相关变量，比如用于存储窗口内数据特征的变量（如窗口内元素之和、最大值等）
    // 2. 扩大窗口（移动右指针）
    // 2.1 在循环中，不断移动右指针right来扩大窗口
    // 2.2 将右指针指向的元素纳入窗口，并根据问题需求更新相关变量。例如，如果要计算窗口内元素之和，就将右指针指向的元素值加到总和变量中
    // 3. 检查窗口是否满足条件
    // 3.1 当右指针移动后，检查窗口是否满足特定的条件，这个条件通常与窗口的大小、窗口内元素的特征等有关。
    // 3.2 如果窗口不满足条件，继续移动右指针扩大窗口；如果满足条件，则进行下一步操作。
    // 4. 更新结果（如果需要）并缩小窗口（移动左指针）
    // 4.1 如果窗口满足条件，根据问题需求更新结果变量。例如，记录当前窗口内的最大值、总和等作为可能的最终结果。
    // 4.2 然后，尝试缩小窗口。移动左指针left，将左指针指向的元素从窗口中移除，并相应地更新相关变量。
    // 5. 重复步骤 2 到 4 直到遍历完整个数组：
    // 5.1 继续移动右指针和左指针，重复上述过程，直到右指针遍历完整个数组。

    // 以下是用 Java 实现的滑动窗口代码示例，以计算给定数组中大小为k的滑动窗口内的元素最大值为例:
    // 在这个例子中，通过双端队列来维护窗口内可能的最大值的索引。随着窗口的滑动，不断更新队列和结果数组。
    // 239. 滑动窗口最大值 https://leetcode.cn/problems/sliding-window-maximum/description/
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {

            // 从队尾移除小于当前元素的值，保持队列单调递减
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 当窗口大小达到k时，记录窗口内的最大值，以k=3为例，当i=2时，窗口第一次完整地覆盖了三个元素，此时可以确定第一个窗口的最大值，并将其添加到结果列表中。
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

//    public static void main(String[] args) {
//        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
//        int[] result = maxSlidingWindow(nums, 3);
//        System.out.println(Arrays.toString(result));
//    }

    /*
    滑动窗口:最小覆盖子串：请你在S中找到包含T中全部字母的最短子串
    思路：
    1. 我们在字符串S中使用双指针的左右指针技巧，初始化left = right = 0,把索引左闭右开区间[left, right)称为一个窗口；
    2. 我们先不断增加right指针扩大窗口[left, right),直到窗口中的字符串符合要求（包含了T中的所有字符）
    3. 此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left,我们都要更新一轮结果。
    4. 重复2和3，直到right到达字符串S的尽头。
     */
    public static String minWindows(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        // 计数器
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        char[] sCharArray = s.toCharArray();
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = sCharArray[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (Objects.equals(window.get(c), need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移除窗口的字符
                char d = sCharArray[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一些列更新
                if (need.containsKey(d)) {
                    if (Objects.equals(window.get(d), need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

//    public static void main(String[] args) {
////        String s = "ADOBECODEBANC";
////        String t = "ABC";
////        String s1 = minWindows(s, t);
////        System.out.println(s1);
//        String s = "ab";
//
//    }

    /*字符串的排列 s1 = "ab" s2 = "eidbaooo"*/
    boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>();
        // 计数器
        Map<Character, Integer> window = new HashMap<>();
        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        char[] charArray = s2.toCharArray();
        while (right < charArray.length) {
            // 扩大right
            char c = charArray[right];
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (Objects.equals(need.get(c), window.get(c))) {
                    valid++;
                }
            }
            // 收缩left
            while (right - left >= s1.length()) {
                // 判断子串是否找到
                if (valid == need.size()) {
                    return true;
                }
                char d = charArray[left];
                left++;
                // 进行窗口内数据的一些列更新
                if (need.containsKey(d)) {
                    if (Objects.equals(window.get(d), need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 未找到符合条件的子串
        return false;
    }

    /*找所有字母异位词： 给定一个字符串S和一个非空字符串T，找打S中所有是T的字母异位词的子串，返回这些子串的起始索引。*/
    /*  输入: s = "cbaebabacd", p = "abc"
        输出: [0,6]
        解释:
        起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
        起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
    */
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录结果
        List<Integer> res = new ArrayList<>();
        char[] charArray = s.toCharArray();
        while (right < charArray.length) {
            char c = charArray[right];
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (Objects.equals(need.get(c), window.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否收缩
            while (right - left >= p.length()) {
                // 当窗口符合条件时 ，把起始索引加入res
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = charArray[left];
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (Objects.equals(need.get(d), window.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        return res;
    }

    /*最长无重复子串：输入一个字符串S,请计算S中不包含重复字符的最长子串长度*/
    /*
        输入: s = "abcabcbb"
        输出: 3
        解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。
    */
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        char[] charArray = s.toCharArray();
        while (right < charArray.length) {
            char c = charArray[right];
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 判断子串是否要收缩
            while (window.getOrDefault(c, 0) > 1) { // 当window.get(c)的值大于1时，说明窗口中存在重复字符，不符合条件，就该移动left缩小窗口
                char d = charArray[left];
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d, window.getOrDefault(d, 0) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int i = lengthOfLongestSubstring(s);
        System.out.println(i);
    }

    static class Checkout {
        private LinkedList<Integer> queue;
        private LinkedList<Integer> maxQueue;
        public Checkout() {
            queue = new LinkedList<>();
            maxQueue = new LinkedList<>();
        }

        public int get_max() {
            if (maxQueue.isEmpty()) {
                return -1;
            }
            return maxQueue.peekFirst();
        }

        public void add(int value) {
            queue.addLast(value);
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
                maxQueue.removeLast();
            }
            maxQueue.addLast(value);
        }

        public int remove() {
            if (queue.isEmpty()) {
                return -1;
            }
            int removedValue = queue.removeFirst();
            if (removedValue == maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
            return removedValue;
        }
    }
}
